| 翻訳と辞書 |
| permutation pattern ： ウィキペディア英語版 |
permutation pattern
In combinatorial mathematics and theoretical computer science, a permutation pattern is a sub-permutation of a longer permutation. A permutation π of length ''n'' is written as a word in one-line notation (i.e., in two-line notation with the first line omitted) as π = π1π2…πn, where πi is the ith number in the word. For example, in the permutation π = 391867452, π1=3 and π9=2. A permutation π is said to ''contain'' the permutation σ if there exists a subsequence of (not necessarily consecutive) entries of π that has the same relative order as σ, and in this case σ is said to be a ''pattern'' of π, written σ ≤ π. Otherwise, π is said to ''avoid'' the permutation σ. For example, the permutation π = 391867452 contains the pattern σ = 51342, as can be seen in the highlighted subsequence of π = 391867452 (or π = 391867452 or π = 391867452 or π = 391867452). Each subsequence (91674, 91675, 91672, 91452) is called a ''copy,'' ''instance,'' or ''occurrence'' of σ. Since the permutation π = 391867452 contains no increasing subsequence of length four, π avoids 1234.
== Early results ==
A case can be made that was the first to prove a result in the field with his study of "lattice permutations".〔.〕 In particular MacMahon shows that the permutations which can be divided into two decreasing subsequences (i.e., the 123-avoiding permutations) are counted by the Catalan numbers.〔, Items 97 and 98.〕
Another early landmark result in the field is the Erdős–Szekeres theorem; in permutation pattern language, the theorem states that for any positive integers ''a'' and ''b'' every permutation of length at least ''ab'' + 1 must contain either the pattern 1, 2, 3, ..., ''a'' + 1 or the pattern ''b'' + 1, ''b'', ..., 2, 1.
抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』
■ウィキペディアで「permutation pattern」の詳細全文を読む
スポンサード リンク
| 翻訳と辞書 : 翻訳のためのインターネットリソース |
Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.
|
|